#ifndef TORJANO_H
#define TORJANO_H
#include <iostream>
#include <map>
#include <utility>
#include <set>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
template<class vertexData, class edgeData>
void BFS(graph<vertexData,edgeData>& g,vertexData vertex,int& time,int& comp,
         map<vertexData,int>& isViseted, map<vertexData,int>& low,
         map<vertexData,int>& component,stack<vertexData>& st){
    typedef typename graph<vertexData,edgeData>::edgeIterator eItt;
    isViseted.erase(vertex);
    isViseted.insert(make_pair(vertex,++(time)));
    low.erase(vertex);
    low.insert(make_pair(vertex,time));
    st.push(vertex);
    for(eItt e = g.findVertex(vertex).beginEdges();e != g.findVertex(vertex).endEdges(); ++e){
        if (isViseted.find(e.second())->second and !component.find(e.second())->second){
            if(low.find(vertex)->second > low.find(e.second())->second){
                low.erase(vertex);
                low.insert(make_pair(vertex,low.find(e.second())->second));
            }
        }
        if (!isViseted.find(e.second())->second){
            BFS(g,e.second(),time,comp,isViseted,low,component,st);
        }
    }
    for(eItt e = g.findVertex(vertex).beginEdges();e != g.findVertex(vertex).endEdges(); ++e){
        if (!component.find(e.second())->second
                && low.find(vertex)->second > low.find(e.second())->second){
            low.erase(vertex);
            low.insert(make_pair(vertex,low.find(e.second())->second));
        }
    }
    if (low.find(vertex)->second == isViseted.find(vertex)->second){
        while(st.top() != vertex)
        {
            component.erase(st.top());
            component.insert(make_pair(st.top(),comp));
            st.pop();
        }
        component.erase(vertex);
        component.insert(make_pair(vertex,comp));
        st.pop();
        ++(comp);
    }
}

template<class vertexData, class edgeData>
void Torjan(graph<vertexData,edgeData>& g,int& size){
    int time = 0;
    int comp = 1;
    typedef typename graph<vertexData,edgeData>::vertexIterator vItt;
    map<vertexData,int> isViseted;//заполним временами входа в вершину
    map<vertexData,int> low;
    map<vertexData,int> component;

    for (vItt v = g.vertexBegin(); v != g.vertexEnd(); ++v){
        isViseted.insert(make_pair(*v,0));
        low.insert(make_pair(*v,size+1));
        component.insert(make_pair(*v,0));
    }

    stack<vertexData> st;
    for (vItt v = g.vertexBegin(); v != g.vertexEnd(); ++v){
        if (!isViseted.find(*v)->second){
            BFS<vertexData,edgeData>(g,*v,time,comp,isViseted,low,component,st);
        }
    }
    vector <vector <vertexData> > components (comp);
    vector<int> counts(comp);

    for (vItt v = g.vertexBegin(); v != g.vertexEnd(); ++v){
        components[component.find(*v)->second-1].push_back(*v);
        counts[component.find(*v)->second-1]++;
    }
    for (int i = comp-1; i >= 0; i --){
        components[i].resize(counts[i]);
        sort(components[i].begin(),components[i].end());
        for (int j = 0 ; j < components[i].size(); j++){
            cout<<components[i][j]<<" ";
        }
        cout<<"\n";
    }
}
#endif // TORJANO_H
